package com.shm.leetcode;

/**
 * 5498. 石子游戏 V
 * 几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。
 *
 * 游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。
 *
 * 只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。
 *
 * 返回 Alice 能够获得的最大分数 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：stoneValue = [6,2,3,4,5,5]
 * 输出：18
 * 解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
 * 在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
 * 最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。
 * 示例 2：
 *
 * 输入：stoneValue = [7,7,7,7,7,7,7]
 * 输出：28
 * 示例 3：
 *
 * 输入：stoneValue = [4]
 * 输出：0
 *
 *
 * 提示：
 *
 * 1 <= stoneValue.length <= 500
 * 1 <= stoneValue[i] <= 10^6
 * @author SHM
 */
public class StoneGameV {

    /**
     * 解题思路：
     * dp[i][j]代表： 从i到j 区间,Alice分数最大值
     * [i x x x x [m] x x x j]
     * 枚举每个m(切割点)
     * 假设我们已经知道dp[i][m]和dp[m+1][j]的值 (这步就是状态转移的突破口)
     *
     * case 1: 如果score[i ~ m] == score[m+1 ~ j]
     * Alice做决定：Alice要获得最大分数，肯定要取max (dp[i][m] ,dp[m+1][j]) + score[i ~ m]
     *
     * case 2: 如果score[i ~ m] != score[m+1 ~ j]
     * Bob会丢弃值最大的行, Alice只能取剩下的
     * 即:如果score[i ~ m] > score[m+1 ~ j]
     *
     * 那么：Alice只能取得 score[m+1 ~ j]+dp[m+1][j]
     * 否则：Alice取得 score[i ~ m]+dp[i,m];
     *
     * (优化)score[i ~ m]: 因为是连续的，可用前缀和优化
     *
     * 作者：MrAQL
     * 链接：https://leetcode-cn.com/problems/stone-game-v/solution/chang-gui-de-qu-jian-dpjian-dan-yi-dong-java-by-mr/
     * @param stoneValue
     * @return
     */
    public int stoneGameV_1(int[] stoneValue) {
        int N = stoneValue.length;
        int[][] dp = new int[N][N];

        //前缀和
        int[] preSum = new int[N];
        preSum[0] = stoneValue[0];
        for (int i=1;i<N;i++){
            preSum[i] = preSum[i-1]+ stoneValue[i];
        }

        //区间dp
        for (int len = 2; len <=N ; len++) {
            for (int i = 0; i+len-1 <N ; i++) {
                int j = i+len-1;
                for (int m = i; m <=j ; m++) {
                    if (i>m || m+1>j){
                        continue;
                    }
                    //左区间
                    int l = dp[i][m];
                    //右区间
                    int r = dp[m+1][j];
                    // i ~ m 分数
                    int ls =  preSum[m] - (i>0? preSum[i-1]:0);
                    //m+1 ~ j 分数
                    int rs = preSum[j]- preSum[m];

                    //case 1: Alice决定丢那行
                    if (ls == rs){
                        int score = Math.max(l,r)+ls;
                        dp[i][j] = Math.max(dp[i][j],score);
                    }
                    //case 2: Bob丢掉最大的，Alice只能选剩下的
                    else{
                        if (ls>rs){
                            dp[i][j] = Math.max(dp[i][j],r+rs);
                        }else{
                            dp[i][j] = Math.max(dp[i][j],l+ls);
                        }
                    }
                }
            }

        }
        return dp[0][N-1];
    }

    int[][] memo;

    /**
     * 解题思路
     * 找到数组的分隔点，然后丢掉数值大的一堆。
     * 此分隔点需要遍历，从0到len - 2（切割后，必须保证石堆有一个元素）。
     * 因为存在大量重复的计算，所以用备忘录记忆已经计算的结果。
     * 该方法为自顶向下的解法。
     *
     * 作者：piaohao
     * 链接：https://leetcode-cn.com/problems/stone-game-v/solution/di-gui-ji-yi-by-piaohao/
     * @param stoneValue
     * @return
     */
    public int stoneGameV(int[] stoneValue) {
        int N = stoneValue.length;
        memo = new int[N][N];
        int[] preSum = new int[N];
        preSum[0] = stoneValue[0];
        for (int i=1;i<N;i++){
            preSum[i] = preSum[i-1]+ stoneValue[i];
        }
        return help(stoneValue, 0, N - 1,0,preSum);
    }
    int help(int[] stoneValue,int lo,int hi,int prev,int[] preSum){
        //当只剩下一个石子时，得0分
        if (lo == hi){
            return 0;
        }
        //当剩下2个石子时，取较小值。根据题意，如果两个石子分值相同，随便丢掉一个，其结果相同。
        if (lo == hi - 1) {
            return prev + Math.min(stoneValue[lo], stoneValue[hi]);
        }
        //如果备忘录存在结果，直接返回
        if (memo[lo][hi] > 0) {
            return memo[lo][hi];
        }
        int res = 0;
        //枚举分隔点
        for (int i = lo; i < hi; i++) {
            //计算左侧的总和
            int l = preSum[i]-(lo>0? preSum[lo-1]:0);
//            for (int j = lo; j <= i; j++) {
//                l += stoneValue[j];
//            }
            //计算右侧总和
            int r = preSum[hi]-preSum[i];
//            for (int j = 0; j <= hi - i - 1; j++) {
//                r += stoneValue[i + j + 1];
//            }
            //两堆石子分值相同，则需要计算丢掉任意一堆后的结果，取较大者
            if (l == r) {
                res = Math.max(res, l + Math.max(help(stoneValue, lo, i, prev,preSum), help(stoneValue, i + 1, hi, prev,preSum)));
            } else if (l > r) {
                //左侧大，则丢掉左侧，递归计算右侧的分值
                res = Math.max(res, r + help(stoneValue, i + 1, hi, prev,preSum));
            } else if (l < r) {
                //右侧大，则丢掉右侧，递归计算左侧的分值
                res = Math.max(res, l + help(stoneValue, lo, i, prev,preSum));
            }
        }
        //备忘录保存结果
        memo[lo][hi] = res;
        return prev + res;
    }
}
